import java.util.ArrayList;
import java.util.List;

public class Solution449 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    private List<Integer> getSplitNumList(String data){
        List<Integer> numList = new ArrayList<>();
        int tmpNum = 0;
        for(int i = 0; i < data.length(); i++){
            char c = data.charAt(i);
            if(c != ';'){
                tmpNum = tmpNum * 10 + c - '0';
            }
            else{
                numList.add(tmpNum);
                tmpNum = 0;
            }
        }
        return numList;
    }

    private int getFirstGreaterInd(List<Integer> numList, int leftEdge, int rightEdge, int target){
        int left = leftEdge, right = rightEdge;
        while(left < right){
            int mid = left + (right - left) / 2;
            int midVal = numList.get(mid);
            if(midVal <= target){
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return numList.get(left) > target ? left : rightEdge + 1; //这时left == right
    }

    private void dfsBuildString(TreeNode tmpNode, StringBuilder stringBuilder){
        if(tmpNode == null){
            return;
        }
        stringBuilder.append(String.valueOf(tmpNode.val) + ';');
        dfsBuildString(tmpNode.left, stringBuilder);
        dfsBuildString(tmpNode.right, stringBuilder);
    }

    private TreeNode dfsBuildTree(List<Integer> numList, int left, int right){
        if(left > right){
            return null;
        }
        int midVal = numList.get(left);
        if(left == right){
            return new TreeNode(midVal);
        }
        int firstGreaterInd = getFirstGreaterInd(numList, left + 1, right, midVal);
        TreeNode tmpNode = new TreeNode(midVal);
        tmpNode.left = dfsBuildTree(numList, left + 1, firstGreaterInd - 1);
        tmpNode.right = dfsBuildTree(numList, firstGreaterInd, right);
        return tmpNode;
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        dfsBuildString(root, stringBuilder);
        return stringBuilder.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()){
            return null;
        }
        List<Integer> numList = getSplitNumList(data);
        return dfsBuildTree(numList, 0, numList.size() - 1);
    }
}
